\input{euler.tex}

\begin{document}

\problem[359]{Hilbert's New Hotel}

An infinite number of people (numbered 1, 2, 3, etc.) are lined up to get a room at Hilbert's newest infinite hotel. The hotel contains an infinite number of floors (numbered 1, 2, 3, etc.), and each floor contains an infinite number of rooms (numbered 1, 2, 3, etc.).
 
Initially the hotel is empty. Hilbert declares a rule on how the $n$th person is assigned a room. Person $n$ gets the first vacant room in the lowest numbered floor satisfying either of the following:

the floor is empty

the floor is not empty, and if the latest person taking a room in that floor is person $m$, then $m + n$ is a perfect square

For example, person 1 gets room 1 in floor 1 since floor 1 is empty. Person 2 does not get room 2 in floor 1 since $1 + 2 = 3$ is not a perfect square. Person 2 instead gets room 1 in floor 2 since floor 2 is empty. Person 3 gets room 2 in floor 1 since $1 + 3 = 4$ is a perfect square. 

Eventually, every person in the line gets a room in the hotel. 

Define $P(f, r)$ to be the person that occupies room $r$ on floor $f$, or 0 if no person occupies the room. For example, $P(1, 1) = 1$, $P(1, 2) = 3$, $P(2, 1) = 2$, $P(10, 20) = 440$, $P(25, 75) = 4863$, $P(99, 100) = 19454$.

Find the sum of all $P(f, r)$ for all positive $f$ and $r$ such that $f \times r$ = $71328803586048$ and give the last 8 digits as your answer.

\solution

We simulate the room assignment for the first 55 guests and display it below.
\begin{center}
\begin{tabular}{c | r r r r r r r r r r r r}
\hline
 $P(f, r)$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
 1 &  1 &  3 &  6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\
 2 &  2 &  7 &  9 & 16 & 20 & 29 & 35 & 46 & 54 \\
 3 &  4 &  5 & 11 & 14 & 22 & 27 & 37 & 44 \\
 4 &  8 & 17 & 19 & 30 & 34 & 47 & 53 \\
 5 & 12 & 13 & 23 & 26 & 38 & 43 \\
 6 & 18 & 31 & 33 & 48 & 52 \\
 7 & 24 & 25 & 39 & 42 \\
 8 & 32 & 49 & 51 \\
 9 & 40 & 41 \\
10 & 50 \\
\hline
\end{tabular}
\end{center}

From this table, we can observe the following pattern for the assignment:
 
1. $P(1,r) = 1 + 2 + \cdots + r = r(r+1)/2$
 
2. If $(f+r)$ is odd, then
\begin{align}
P(2,r) &= P(1,r+1) - 1 \notag \\
P(3,r) &= P(1,r+1) - 1 \notag \\
P(f,r) &= P(f-2,r+2) - 1 \notag 
\end{align}

3. If $(f+r)$ is even, then
\begin{align}
P(2,r) &= P(1,r+1) + 1 \notag \\
P(3,r) &= P(1,r+1) + 1 \notag \\
P(f,r) &= P(f-2,r+2) + 1 \notag
\end{align}

Now that we have obtained closed-form formula for $P(f,r)$, we just need to enumerate the divisors of $71328803586048 = 2^{27} \times 3^{12}$ to compute the answer. 

\answer

40632119

\complexity

Computing $P(f,r)$ takes constant time and space. Suppose we have already factorized the product, and let $d$ be the number of divisors of the product. Then it follows that:

Time complexity: $\BigO(d)$

Space complexity: $\BigO(1)$

\end{document} 